<html>
<META http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<head>
<title>Section 20.2.&nbsp; History</title>
<link rel="STYLESHEET" type="text/css" href="images/style.css">
<link rel="STYLESHEET" type="text/css" href="images/docsafari.css">
</head>
<body>
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr><td><div STYLE="MARGIN-LEFT: 0.15in;"><a href="toc.html"><img src="images/team.gif" width="60" height="17" border="0" align="absmiddle"  alt="Team BBL"></a></div></td>
<td align="right"><div STYLE="MARGIN-LEFT: 0.15in;">
<a href=ch20lev1sec1.html><img src="images/prev.gif" width="60" height="17" border="0" align="absmiddle" alt="Previous Page"></a>
<a href=ch20lev1sec3.html><img src="images/next.gif" width="60" height="17" border="0" align="absmiddle" alt="Next Page"></a>
</div></td></tr></table>
<br><table width="100%" border="0" cellspacing="0" cellpadding="0"><tr><td valign="top"><a name="ch20lev1sec2"></a>
<h3 class="docSection1Title">20.2. History</h3>
<p class="docText">One popular library of database functions in the UNIX System is the <tt>dbm</tt>(3) library. This library was developed by Ken Thompson and uses a dynamic hashing scheme. It was originally provided with Version 7, appears in all BSD releases, and was also provided in SVR4's BSD-compatibility library [<a class="docLink" href="bib01.html#biblio01_009">AT&amp;T 1990c</a>]. The BSD developers extended the <tt>dbm</tt> library and called it <tt>ndbm</tt>. The <tt>ndbm</tt> library was included in BSD as well as in SVR4. The <tt>ndbm</tt> functions are standardized in the XSI extensions of the Single UNIX Specification.</P>
<p class="docText"><a name="idd1e148498"></a><a name="idd1e148501"></a><a name="idd1e148504"></a><a name="idd1e148509"></a><a name="idd1e148514"></a><a name="idd1e148521"></a><a name="idd1e148526"></a><a name="idd1e148533"></a><a name="idd1e148536"></a><a name="idd1e148539"></a><a name="idd1e148544"></a><a name="idd1e148547"></a><a name="idd1e148550"></a><a name="idd1e148553"></a><a name="idd1e148556"></a><a name="idd1e148559"></a><a name="idd1e148562"></a><a name="idd1e148565"></a><a name="idd1e148568"></a><a name="idd1e148571"></a>Seltzer and Yigit [<a class="docLink" href="bib01.html#biblio01_057">1991</a>] provide a detailed history of the dynamic hashing algorithm used by the <tt>dbm</tt> library and other implementations of this library, including <tt>gdbm</tt>, the GNU version of the <tt>dbm</tt> library. Unfortunately, a basic limitation of all these implementations is that none allows concurrent updating of the database by multiple processes. These implementations provide no type of concurrency controls (such as record locking).</P>
<p class="docText">4.4BSD provided a new <tt>db</tt>(3) library that supports three forms of access: (a) record oriented, (b) hashing, and (c) a B-tree. Again, no form of concurrency was provided (as was plainly stated in the BUGS section of the <tt>db</tt>(3) manual page).</p>
<blockquote>
<p class="docText">Sleepycat Software (<a class="docLink" target="_blank" href="http://www.sleepycat.com">http://www.sleepycat.com</a>) provides versions of the <tt>db</tt> library that do support concurrent access, locking, and transactions.</P>
</blockquote>
<p class="docText">Most commercial database libraries do provide the concurrency controls required for multiple processes to update a database simultaneously. These systems typically use advisory locking, as we described in <a class="docLink" href="ch14lev1sec3.html#ch14lev1sec3">Section 14.3</a>, but they often implement their own locking primitives to avoid the overhead of a system call to acquire an uncontested lock. These commercial systems usually implement their database using B+ trees [<a class="docLink" href="bib01.html#biblio01_016">Comer 1979</a>] or some dynamic hashing technique, such as linear hashing [<a class="docLink" href="bib01.html#biblio01_041">Litwin 1980</a>] or extendible hashing [<a class="docLink" href="bib01.html#biblio01_018">Fagin et al. 1979</a>].</P>
<p class="docText"><a class="docLink" href="#ch20fig01">Figure 20.1</a> summarizes the database libraries commonly found in the four operating systems described in this book. Note that on Linux, the <tt>gdbm</tt> library provides support for both <tt>dbm</tt> and <tt>ndbm</tt> functions.</P>
<a name="ch20fig01"></a><p><table cellspacing="0" class="allBorders" border="1" RULES="groups" cellpadding="5"><caption><H5 class="docTableTitle">Figure 20.1. Support for database libraries on various platforms</H5></caption><colgroup><col width="100"><col width="100"><col width="90"><col width="60"><col width="90"><col width="50"></colgroup><thead><TR><th class="rightBorder bottomBorder thead" scope="col" align="left" valign="middle"><p class="docText"><span class="docEmphRoman">Library</span></p></th><th class="rightBorder bottomBorder thead" scope="col" align="center" valign="middle"><p class="docText"><span class="docEmphRoman">POSIX.1</span></P></th><th class="bottomBorder thead" scope="col" align="center" valign="bottom"><p class="docText"><span class="docEmphRoman">FreeBSD 5.2.1</span></p></th><th class="bottomBorder thead" scope="col" align="center" valign="bottom"><p class="docText"><span class="docEmphRoman">Linux 2.4.22</span></P></th><th class="bottomBorder thead" scope="col" align="center" valign="bottom"><p class="docText"><span class="docEmphRoman">Mac OS X 10.3</span></P></th><th class="bottomBorder thead" scope="col" align="center" valign="bottom"><p class="docText"><span class="docEmphRoman">Solaris 9</span></P></th></tr></thead><TR><TD class="rightBorder" align="left" valign="top"><p class="docText"><tt>dbm</tt></p></TD><TD class="rightBorder" align="left" valign="top"><p class="docText"></p></td><td class="docTableCell" align="left" valign="top">&nbsp;</td><TD class="docTableCell" align="center" valign="top"><p class="docText"><tt>gdbm</tt></p></TD><td class="docTableCell" align="left" valign="top">&nbsp;</TD><td class="docTableCell" align="center" valign="top"><p class="docText">&#8226;</p></td></tr><tr><td class="rightBorder" align="left" valign="top"><p class="docText"><tt>ndbm</tt></p></td><td class="rightBorder" align="center" valign="top"><p class="docText">XSI</p></td><td class="docTableCell" align="center" valign="top"><p class="docText">&#8226;</p></td><td class="docTableCell" align="center" valign="top"><p class="docText"><tt>gdbm</tt></p></td><TD class="docTableCell" align="center" valign="top"><p class="docText">&#8226;</P></td><TD class="docTableCell" align="center" valign="top"><p class="docText">&#8226;</P></TD></tr><TR><TD class="rightBorder" align="left" valign="top"><p class="docText"><tt>db</tt></P></td><TD class="rightBorder" align="left" valign="top"><p class="docText"></p></TD><TD class="docTableCell" align="center" valign="top"><p class="docText">&#8226;</P></td><TD class="docTableCell" align="center" valign="top"><p class="docText">&#8226;</P></td><TD class="docTableCell" align="center" valign="top"><p class="docText">&#8226;</P></td><td class="docTableCell" align="center" valign="top"><p class="docText">&#8226;</p></td></TR></table></p><BR>

<a href="17021535.html"><img src="images/pixel.gif" alt="" width="1" height="1" border="0"></a><ul></UL></td></tr></table>
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr><td><div STYLE="MARGIN-LEFT: 0.15in;"><a href="toc.html"><img src="images/team.gif" width="60" height="17" border="0" align="absmiddle"  alt="Team BBL"></a></div></td>
<td align="right"><div STYLE="MARGIN-LEFT: 0.15in;">
<a href=ch20lev1sec1.html><img src="images/prev.gif" width="60" height="17" border="0" align="absmiddle" alt="Previous Page"></a>
<a href=ch20lev1sec3.html><img src="images/next.gif" width="60" height="17" border="0" align="absmiddle" alt="Next Page"></a>
</div></td></tr></table>
</body></html><br>
<table width="100%" cellspacing="0" cellpadding="0"
style="margin-top: 0pt; border-collapse: collapse;"> 
<tr> <td align="right" style="background-color=white; border-top: 1px solid gray;"> 
<a href="http://www.zipghost.com/" target="_blank" style="font-family: Tahoma, Verdana;
 font-size: 11px; text-decoration: none;">The CHM file was converted to HTM by Trial version of <b>ChmD<!--224-->ecompiler</b>.</a>
</TD>
</TR><tr>
<td align="right" style="background-color=white; "> 
<a href="http://www.etextwizard.com/download/cd/cdsetup.exe" target="_blank" style="font-family: Tahoma, Verdana;
 font-size: 11px; text-decoration: none;">Download <b>ChmDec<!--224-->ompiler</b> at: http://www.zipghost.com</a>
</TD></tr></table>
